The problem can be found at the following link: Question Link
By intuition, this problem can be solved using dynamic programming (DP) techniques. The basic idea is to find the maximum possible value obtainable by cutting a rod of length n
into smaller pieces and selling them according to their respective lengths. For a detailed understanding, you can refer to this tutorial.
- Time Complexity:
O(n^2)
because we use nested loops to calculate the values ofdp[i]
for each length from 1 to n. - Auxiliary Space Complexity:
O(n)
because we use an additional arraydp
of sizen+1
to store the optimal values.
class Solution{
public:
int cutRod(int price[], int n) {
int dp[n][n+1];
for(int i=0;i<=n;++i)
dp[0][i] = i*price[0];
for(int i = 1; i<n;++i){
for(int rs = 0; rs<=n;++rs){
int ntake = dp[i-1][rs];
int take = 0;
if(rs>=i+1)
take = dp[i][rs - i - 1] + price[i];
dp[i][rs] = max(take,ntake);
}
}
return dp[n-1][n];
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.